#include <bits/stdc++.h>

class Factorial
{
public:
    Factorial(int N, int mod) : mod(mod)
    {
        N += 1;
        f.resize(N, 1);
        g.resize(N, 1);
        for (int i = 1; i < N; ++i)
        {
            f[i] = f[i - 1] * i % mod;
        }
        g[N - 1] = pow_mod(f[N - 1], mod - 2, mod);
        for (int i = N - 2; i >= 0; --i)
        {
            g[i] = g[i + 1] * (i + 1) % mod;
        }
    }

    int fac(int n) const
    {
        return f[n];
    }

    int fac_inv(int n) const
    {
        return g[n];
    }

    int combi(int n, int m) const
    {
        if (n < m || m < 0 || n < 0)
        {
            return 0;
        }
        return f[n] * g[m] % mod * g[n - m] % mod;
    }

    int permu(int n, int m) const
    {
        if (n < m || m < 0 || n < 0)
        {
            return 0;
        }
        return f[n] * g[n - m] % mod;
    }

    int catalan(int n) const
    {
        return (combi(2 * n, n) - combi(2 * n, n - 1)) % mod;
    }

    int inv(int n) const
    {
        return f[n - 1] * g[n] % mod;
    }

private:
    int mod;
    std::vector<int> f;
    std::vector<int> g;

    long long pow_mod(long long base, long long exp, long long mod) const
    {
        long long res = 1;
        for (; exp; exp /= 2)
        {
            if (exp % 2)
                res = res * base % mod;
            base = base * base % mod;
        }
        return res;
    }
};

int main()
{
    Factorial fact(2 * 100000, 99876543);
    return 0;
}